package utils;

public class MathUtils {
	
	public static int pgcd (int a, int b)
	{
		assert a > 0;
		assert b > 0;
		if(a == b) return a;
		if(b == 1) return 1;
		if(a == 1) return 1;
		
		int _m = Math.max(a,b);
		int _n = Math.min(a,b);
		int r = _m % _n;
		while (r > 0)
		{
			r = _m % _n;
			if(r == 0) break;
			_m = Math.max(_n,r);
			_n = Math.min(_n,r);
		}
		return _n;
	}
	
	
	public static long pgcd (long a, long b)
	{
		assert a > 0;
		assert b > 0;
		if(a == b) return a;
		if(b == 1) return 1;
		if(a == 1) return 1;
		
		long _m = Math.max(a,b);
		long _n = Math.min(a,b);
		long r = _m % _n;
		while (r > 0)
		{
			r = _m % _n;
			if(r == 0) break;
			_m = Math.max(_n,r);
			_n = Math.min(_n,r);
		}
		return _n;
	}
	
}
